This invention relates to a system for correcting all single and double errors and for detecting all triple errors in data recording or data transmission.
In data communication systems it is important to incorporate data error detection and/or data error correction facilities. When data is transmitted from point to point, transmission line noise or interruptions can introduce errors which must be detected and/or corrected if the data integrity is to be maintained. Likewise, in recording and recovering data from memory, error detection and/or correction is required to insure that the data has not changed while in storage or during recovery.
A known technique employed in the past has involved the use of cyclical redundancy codes for the generation of parity bits which are transmitted or stored together with the data bits. See, for example, "Error Correcting Codes" by W. W. Peterson, MIT Press, 1961. In such systems the integrity of the data bits can be determined by again generating a set of parity bits from the recovered data bits and comparing the new parity bits with the previously encoded parity bits. If the new parity bits are identical to the previously encoded parity bits, error free data can be assumed.
In the usual procedure the parity bits are derived by operating on the serial data bits of the data message as though they are coefficients of a long binary polynomial D(X). Mathematically, the data polynomial is divided by a generator polynomial G(X) producing a quotient Q(X) and error remainder R(X). EQU d(x)/g(x) = q(x) + r(x). (1)
The quotient is discarded and R(X) is used as a set of parity bits. The parity bits P(X) are concatenated to the data bits D(X). Thus, the encoded message word M(X) that is transmitted or recorded is represented: EQU M(X) = D(X) + P(X). (2)
when checking a previously encoded word N(X) to determine if the data portion is correct, it is divided by the same polynomial generator to derive error parity bits E(X): EQU n(x)/g(x) = q(x) + e(x). (3)
if the previously encoded parity bits agree with the error detection parity bits, then N(X) = D(X) and error free transmission can therefore be assumed.
Although cyclical redundancy codes usually employ a serial implementation, parallel implementations are known. See, for example, "Parallel CRC lets many lines use one circuit" by Arun K. Pandeya and Thomas J. Cassa, Computer Design, September, 1975, Vol. 14, No. 9, pages 87-91.
Where the generator polynomial is selected such that the difference between the original parity bits and the error detection parity bits yield error decodes which can be uniquely correlated to specific errors, these error decodes can also be used to achieve error correction.